

			SPRE CULMI - SOLUTIE
		       -----------------------

	Ideea de rezolvare este urmatoarea: se baleiaza vectorul de la stanga la dreapta, pentru a
se construi subsirurile dintr-o singura parcurgere. Fiecare element este adaugat la sfarsitul unuia
dintre subsirurile deja formate sau, daca acest lucru nu este posibil, el este pus separat pentru
a incepe un nou subsir.
	Fie exemplul dat: N=7, V=(9,2,4,7,10,11,8). Atunci primul element (9) va fi in mod evident
inceputul unui subsir. De asemenea si 2, deoarece el nu poate fi pus in acelasi subsir cu 9. Ele-
mentul 4 se leaga de 2 (este asezat in acelasi subsir cu el), pentru ca nu se poate lega de 9, si
ar fi o pierdere inutila sa il asezam intr-un subsir separat. Elementul 7 se leaga de subsirul deja
format (2,4). Ce se intampla insa cu elementul 10? El poate fi atasat atat subsirului (9), cat si
subsirului (2,4,7).
	In situatiile in care un element poate fi alipit la mai multe subsiruri, se prefera alipirea
la subsirul care se termina intr-un numar cat mai mare. De ce? Daca alipim 10 la subsirul (2,4,7),
obtinem subsirurile (2,4,7,10) si (9). Daca insa il alipim la (9), obtinem (2,4,7) si (9,10). In
primul caz, capetele subsirurilor aveau valorile 10 si 9; in acest caz, capetele subsirurilor au
valorile 7 si 10.; aceasta varianta este mai folositoare deoarece capetele subsirurilor sunt mai
mici, ceea ce este bine pentru alipirea in continuare a altor numere (cum este numarul 8, de exem-
plu). Daca s-ar fi alipit 10 la subsirul (2,4,7), s-ar fi obtinut in final 3 subsiruri : (9), (2,
4,7,10,11) si (8), adica o solutie neoptima.
	In concluzie, pentru fiecare element V[i] trebuie sa aflam, dintre toate subsirurile deja
create, capatul cu valoarea cea mai mare, dar strict mai mica decat V[i]. Pentru aceasta se reco-
manda mentinerea valorilor de la capetele subsirurilor intr-un vector separat, sortat, asupra ca-
ruia se pot efectua cautari binare. De asemenea, vom retine pentru fiecare element V succesorul
sau in subsirul crescator din care face parte.
	Pentru fiecare element din vector se efectueaza deci o cautare binara, ca urmare complexi-
tatea algoritmului are ordinul O(N*logN).